package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/09/01
 */
public class 第413场单周赛 {

    public static void main(String[] args) {


    }

    public boolean checkTwoChessboards(String coordinate1, String coordinate2) {

        int[][] ints = {
                {0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0},
                {0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0}
        };

        return ints[coordinate1.charAt(0) - 'a'][coordinate1.charAt(0) - '1'] ==
                ints[coordinate2.charAt(0) - 'a'][coordinate2.charAt(0) - '1'];

    }

    public int[] resultsArray(int[][] queries, int k) {
        int[] ans = new int[queries.length];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 0; i < queries.length; i++) {

            priorityQueue.add(Math.abs(queries[i][0]) + Math.abs(queries[i][1]));

            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }

            if (priorityQueue.size() < k) {
                ans[i] = -1;
                continue;
            }

            ans[i] = priorityQueue.peek();
        }

        return ans;
    }

    private int[][] visit;

    // key-数字 value-对应出现的行号
    Map<Integer, Set<Integer>> map = new HashMap<>();

    public int maxScore(List<List<Integer>> grid) {
        int max = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(i).size(); j++) {
                Set<Integer> set = map.get(grid.get(i).get(j));
                if (set == null) {
                    set = new HashSet<>();
                    map.put(grid.get(i).get(j), set);
                }
                set.add(i);
                max = Math.max(max, grid.get(i).get(j));
            }
        }

        visit = new int[max + 1][1 << grid.size()];
        for (int[] ints : visit) {
            Arrays.fill(ints, -1);
        }
        return dfs(max, 0);
    }

    // 已经选了 j 集合里面的数字，对应数字 i 选或者不选
    // j 用一个数字记录，它是一个 10 位的二进制，1 代表第一行已经选了，初始值为 0
    private int dfs(int i, int j) {
        if (i == 0) {
            return 0;
        }
        if (visit[i][j] != -1) {
            return visit[i][j];
        }

        // 不选
        int ans = dfs(i - 1, j);

        Set<Integer> set = map.get(i);
        if (set != null) {
            // 选
            for (Integer row : set) {
                // row 行没选过
                if ((j >> row & 1) == 0) {
                    ans = Math.max(ans, i + dfs(i - 1, j | 1 << row));
                }
            }
        }
        return visit[i][j] = ans;
    }
}
